package com.zyk.grate_offer.class12;

import java.util.HashMap;

/**
 * @author zhangsan
 * @date 2021/6/5 11:37
 */
public class Code01_FindAnagramInStr {

    // 在s中找到子串为 aim的变形词的位置
    // 变形词:　字符数量相等，字符相等，字符顺序可以不相等
    public static int findAnagramInstr(String s, String aim) {
        int N = s.length(), winLen = aim.length();
        HashMap<Character, Integer> need = new HashMap<>();
        for (char c : aim.toCharArray())
            need.put(c, need.getOrDefault(c, 0) + 1);
        char[] str = s.toCharArray();
        int distance = winLen;
        int l = 0, r = 0;
        while (r < N) {
            if (r - l < winLen) {    // 窗口没有形成
                if (need.containsKey(str[r])) {
                    int cnt = need.get(str[r]) - 1;
                    need.put(str[r], cnt);
                    if (cnt >= 0) distance--;
                }
                r++;
            } else {
                if (need.containsKey(str[r])) {
                    int cnt = need.get(str[r]) - 1;
                    need.put(str[r], cnt);
                    distance--;
                }
                if (need.containsKey(str[l])) {
                    int cnt = need.get(str[l]) + 1;
                    need.put(str[r], cnt);
                    distance++;
                }
                l++;
                r++;
            }
            if (distance == 0) return l;
        }
        return -1;
    }


    public static boolean checkInclusion(String s1, String s2) {
        int N = s2.length(), winLen = s1.length();
        if(N < winLen) return false;
        HashMap<Character, Integer> need = new HashMap<>();
        for (char c : s1.toCharArray())
            need.put(c, need.getOrDefault(c, 0) + 1);
        char[] str = s2.toCharArray();
        int distance = winLen;
        int l = 0, r = 0;
        while (r < winLen) {
            if (need.containsKey(str[r])) {
                int cnt = need.get(str[r]) - 1;
                need.put(str[r], cnt);
                if (cnt >= 0)
                    distance--;
            }
            r++;
        }
        while (r < N) {
            if (distance == 0) return true;
            if (need.containsKey(str[r])) {
                int cnt = need.get(str[r]) - 1;
                need.put(str[r], cnt);
                if (cnt >= 0)
                    distance--;
            }
            if (need.containsKey(str[l])) {
                int cnt = need.get(str[l]) + 1;
                need.put(str[l], cnt);
                if (cnt > 0)
                    distance++;
            }
            l++;
            r++;
        }
        return distance == 0;
    }

    // for test
    public static void main(String[] args) {
//        String str = "adcabccasjdklasjdl",
//                aim = "accab";
//        System.out.println(findAnagramInstr(str, aim));
//        String s1 = "adc"
//                , s2 = "dcda";
        String s1 = "ab"
                , s2 = "a";
        System.out.println(checkInclusion(s1, s2));
    }

}
